MastersForum

Sprache egal?

OK ich Versuchs ma Morgen willst Compilierte exe oder Quellcode oder beides?^^

soll die dabei längstmögliche wörterkette enstehen oder einfach nur ne wörterkette, bis kein wort mehr angehängt werden kann ?

substr(wort, length(wort)-3, 3)
und
substr(wort, 1,3)

iss eigentlich alles was du brauchst, der rest iss nur schreibarbeit

Du bekommst ein Problem mit der Laufzeit bei einigermassen vielen Worten (Pi mal Daumen bei 100 bis 200), wenn ich mich nicht irre.

Ich schlage einen Algorithmus ähnlich dem eines Schachprogramms vor, also mit Suchbäumen, das würde die rechenzeit wesentlich verlangsamen, aber ich denke dass geht über das hinaus, was das Programm leisten soll...

yep, ich denke, der ansatz von maxpower ist genau der richtige.

Hm, einigermassen optimale Laufzeit für das Problem maybe:

Mach ne Hashtable, in denen du Vektoren von Wörtern schreibst, mit den ersten 3 Buchstaben der Wörter als Key für den Hash.

Dann fangst mit nem zufälligen Wort an, holst dir den entsprechenden Vektor für die 3 Buchstaben, nimmst ein Wort raus & löschst es aus dem Vektor. Das erste mal wenn du entweder Keinen Vektor findest, oder er Leer is -> biste fertig

Laufzeit sollte hier O(n) sein, da Hashtable Zugriffe ~konstant?

Anm: Die Laufzeit bei ner Lösung mit Suchbäumen sollte O(n*log(n)) sein.

In pseudo-java

initialisiern:
h= new Hashtable();

foreach(wordinlist) //lasse 1 wort zum anfangen übrig
{
vector v=h.get(wordinlist.erste3buchstaben);
if(v==null)
{
v=new vector();
h.put(v,wordinlist.erste3buchstaben);
}
v.add(wordinlist);
}

kette machen
String wortkette=übrigeswort; //starte mit dem übrigen wort...
String wort;
do
{
vector v=h.get(wortkette.letzte3buchstaben)
if(v==null ||v.size()==0)
{wort=null;} //fertig...
else
{
wort=v.get(0);
v.remove(wort);
wortkette+=wort;
}
}while(wort!=null);

Die Lösung bringt natürlich net die optimale Kette (längste mögliche Kette) sondern nur eine zufällige Kette. Die längste mögliche Kette zu finden hat sicher ne exponentielle Laufzeit...:

ca:
v -> Verzweigungsgrad ->
Durchschnittliche Anzahl d. Wörter mit Gleichen 3 Anfangsbuchstaben

n -> Anzahl der Wörter
k -> Länge d. längsten Kette

Laufzeit ~ O(n*v^k) ?

greets

So, mir war bisserl fad

Hab das Teil mal mit Greedy-Search geproggt. Damit findet man für 3 Buchstaben im Openoffice-Wörterbuch immerhin Ketten bis 1500 Wörter

Als Heuristik:
Wenn mehrere Wörter möglich sind suche das Wort aus, für dessen Ende es die meisten passenden Wörter gibt.

Zum Vergleich: Aus 1.000.000 zufällig generierten Ketten (ohne Heuristik) war die Längste 44 Wörter lang.

Zip mit jar (incl Source) & Wortliste gibts hier

hf

PS:
Wenn jemand Freude an Wortketten hat:
Deutsche Wortkette @ 1500 Wörter (250ms Suchzeit aus dem OpenOffice Dictionary generiert)
Englische Wortkette @ 8800 Wörter (1800ms Suchzeit aus dieser Wortliste generiert)

procedure TWoerterkette.FormCreate(Sender: TObject);
var WoerterListe, FertigeWoerterListe: TStringList;
Start, Gefunden: Boolean;
Text, Suchen, Wort: String;
i, n, r, w: Integer;
begin
If OpenDialog1.Execute then
begin
TextListBox.Items.LoadFromFile(OpenDialog1.Filename);
Start:=True;
end //öffnet das Textdokument und läd es in eine TListBox
else
begin
Application.Terminate;
Start:=False;
end; //Im Falle eines Abbruchs wird das Programm Geschlossen
If Start=True then
begin
Text:='';
i:=0;
while i<TextListBox.Items.Count do
begin
Text:=Text+' '+TextListBox.Items;
end; //Die Liste wirt zu einem einzigen String zusammengefügt um das Bearbeiten zu erleichtern
WoerterListe:=TStringList.Create;
try
WoerterListe.Delimiter:=' ';
WoerterListe.DelimitedText:=Text;
finally
begin
WoerterListBox.Items:=WoerterListe;
WoerterListe.Free;
end;
end; //Der String wird in seine Bestandteile zerlegt
FertigeWoerterListe:=TStringList.Create;
try
FertigeWoerterListe.Add(WoerterListBox.Items[WoerterListBox.Items.Count]);//Er beginnt mit dem ersten Wort falls es dazu keine ergänzungen gibt ist hier schon schluß^^
r:=0;
While r<WoerterListBox.Items.Count do
begin
Wort:=WoerterListBox.Items[r];
Laenge.Text:=Wort;
n:=Laenge.GetTextLen;
Suchen:=Wort;
Delete(Suchen,0,n-3);
If Suchen<>'' then
begin
Gefunden:=False;
w:=-1;
while (w<WoerterListBox.Items.Count-1) and not Gefunden do
begin
inc(w);
If Pos(Suchen, WoerterListBox.Items[w])>0 then Gefunden:=True;
end;
If Gefunden=True then
begin
FertigeWoerterListe.Add(WoerterListBox.Items[w]);
WoerterListBox.Items.Delete(r);
r:=r+1;
end
else r:=r+1;
end;
end;// Er geht in der Reihenfolge vor und löscht ergänzte Wörter. Am Ende fängt er von Vorne an mit den Wörtern die noch drine sind und das Solange bis er keins mehr ergänzen kann.
finally
begin
WoerterListBox.Items.Clear;
WoerterListBox.Items:=FertigeWoerterListe;
FertigeWoerterListe.Free;
end;// Die Virtuelle Liste wird nun in Einer ListBox gespeichert.
end;
end;
end;

Hatte nicht wirklich viel Zeit weiß nicht ob es geht aber glaub im Hauptteil nen großen Fehler zu haben. In der Schule benutzt man meist Delphi deshalb einfach 2 Listboxes einfügen eine in WoerterListBox und die andere in TextListbox umbenennen, aus der Registerkarte Dialoge noch einen OpenDialog. Den Code im OnCreate-Ereignis der HauptForm einfügen und hoffen das er funktioniert . Mein erster versuch seit fast nem halben Jahr Bin nur Hobby Progger der das vor nem Jahr in der Schule hatte. Wenns nicht geht kann ich mich ja nochma versuchen^^

@Ramses:

@Krypton:
Post besser nen link zu ner geuppten version. Da das Board sämtliche Einrückungen entfernt is geposteter Code hier Horror zu lesen

http://thales.xardas.lima-city.de/Code.txt

@NilPferd:

Quoted

Schreibe ein Programm, das aus einer Liste von Wörtern eine möglichst lange Wörter-Kette erzeugt.

Da ne vollständige Suche hier exponentielle Laufzeit hat und ihr ja anscheinend ne relativ lange Wortliste kriegt, lässt sich die optimale Lösung nicht in vertretbarer Laufzeit finden. (Wie Sheep ja schon richtig gesagt hat )

Wenn du also kein Bock auf proggen hast, gehste einfach zum Lehrer und sagst ihm die Angabe is eigentlich shice, weil ein Programm das du strikt nach der Angabe proggst net terminiern wird.

Falls dir das zu radikal is :
Kann man das, imo, nur mit Heuristiken sinnvoll lösen - n Vorschlag dazu is ja oben gepostet. Die finden aber natürlich *nicht immer* die optimale Lösung, aber ich nehm mal an das die Angabe in diese Richtung gemeint war. Geht sicherlich noch besser als oben (mit Backtracking?), aber kA wie gut das sein muss/soll.

@Krypton:
Ich kann zwar kein Delphi, sieht aber von der Idee her richtig aus (kA bzgl Syntax). Allerdings findest du "nur" eine zufällige Lösung bei Laufzeit O(k*n) mit k=Kettenlänge, n=Wortanzahl.

Wenn man von einer begrenzten Wörterkette ausgeht und einem anständigen prozessor, dazu ein gescheiter algorithmus, sollte sich auf jeden fall ein ergebnis ergeben, dass in vertretbarer zeit gefunden wird.

ansonsten würden die schachcomputer auch nicht weltermeister besiegen

die anzahl der durchläufe is ja maximal n!, aber durch die suche in einem baummuster, sollte sich die anzahl der möglichkeiten drastsich reduzieren lassen, vielleicht hat ja einer ne ahnung und kann das realistsich abschätzen, ich kann das mit meinen bescheidenen kenntnissen leider nicht

Wahrscheinlich hoffen die Lehrkräfte in der Informatik, dass irgendwann einer der Millionen Schüler zufällig P=NP zeigt (Insider-Bemerkung, Erklärung bräuchte schätzungsweise einen Aufsatz über 5000 Wörter).

@Nilpferd: Wenn du das erst zum Dienstag oder später brauchst und du magst, schreibe ich dir auch eine Abschätzung zur Laufzeit. Das wäre als Alternative zur Problemlösung auch nicht schlecht. Nur wird es schwer werden, das als selbstgemacht zu verkaufen.

EDIT: @Max: Ich schreibe mal morgen meine Abschätzung hin (ohne Anspruch auf 100%ige Richtigkeit, bin ja selbst nur Student), erstmal muss ich ins Bett...

jo sheep, würde mich schon interressieren, was du als mathematiker dazu sagst ^^

n8

Hmm das mit dem Schlafen war wohl nichts. Nach drei Stunden wach daliegen und über das Problem nachdenken poste ich es wohl doch besser jetzt.

Erstmal den worst case, also den schlechtesten Fall...

Von n Wörtern sind n-1 vom Typ "Kerker", also beliebig kombinierbar. Es bleibt ein Wort, zum Beispiel "Automobil", das aus dem Rahmen fällt.

Das Programm setzt nun jedes Wort als Startwort ein. Sobald eins der n-1 "Kerker" verwendet wurde, kann als zweites Wort eins der verbliebenen n-2 "Kerker" eingesetzt werden. Das geht immer so weiter, mit "Kerker" als Startwort bekommt man immer eine n-1 Wörter lange Kette "KerkerKerker...Kerker", in der nur das "Automobil" fehlt.

Da das Programm aber nur n-1 Wörter lange Ketten findet, bricht es nicht ab und sucht bis zum bitteren Ende nach einer n Wörter langen Kette. Die gibt es natürlich in dem Fall nicht, wegen "Automobil", aber Computer sind ja schliesslich doof.

Jedenfalls wird das Programm sehr fleissig herumprobieren, nämlich (n-1)*(n-2)*(n-3)*...*1 Wege, die immer zu derselben Kette "KerkerKerker...Kerker" führen. Die (n-1)*...*1 kann man zu (n-1)!, also einer Fakultät, zusammenfassen. Das "Automobil" verursacht nur einmal Vergleiche mit den n-1 "Kerkern", der Aufwand dafür fällt nicht ins Gewicht.

Mit n "Kerker"n klappt es nicht, weil das Programm da sofort eine Kette der Länge n findet und dann aufhören sollte (bei durchdachter Programmierung, denn warum sollte man dann weitersuchen?).

Insgesamt ist die Laufzeit also exponentiell und wächst mit jedem weiteren Wort rasend schnell. Allerdings ist dieser worst case extrem unwahrscheinlich, also habe ich mich weiter damit beschäftigt...

Ok, für den durchschnittlichen Fall wird es ziemlich kompliziert, ich denke mal, es ist an Beispielen viel anschaulicher.

Zunächst muss ich aber die Einschränkung machen, dass die End- und Anfangsbuchstaben rein zufällig sind. Ohne Wissen über den Eingabe-Datensatz lässt es sich kaum besser machen (ok, man könnte einen Duden per Programm analysieren, welche Endungen und Anfangsbuchstaben am häufigsten vorkommen - aber soviel ist mir das Problem doch nicht wert ).

Ich gehe also von zufälligen Endbuchstaben- und Anfangsbuchstaben-Dreierpacks aus. Zugelassen sind das Alphabet, die drei Umlaute und das "ß", also 30 Buchstaben. Es macht nicht wirklich einen Unterschied, ob man 26 oder 30 oder 40 Buchstaben ansetzt, sieht man später. Die 30 sind jedenfalls recht bequem für meine Zwecke. Drei Buchstaben hintereinander mit jeweils 30 verschiedenen Möglichkeiten ergeben insgesamt 30 * 30 * 30 Dreierpacks, also satte 27000.

Fangen wir mal an, Wort für Wort...

1. Wort

Hier nimmt man einfach nur das erste Wort der Datei, das zweite etc. . Kümmern wir uns zunächst das erste.

2. Wort

Unser erstes Wort hat nun eine festgelegte Endung. Die Chance, dass ein weiteres Wort diese drei Buchstaben zufällig als Anfang hat, ist ziemlich gering - 1 zu 27000. Entsprechend ist die Chance, dass das Wort nicht passt, 26999 zu 27000, fast 100% also.

Aber wir haben ja n-1 Kandidaten (ursprünglich waren es n Wörter, eins wurde erstes Wort). Die Chance, dass keins davon passt, ist 26999 zu 27000 pro Kandidat. Mathematisch ausgedrückt...

P(nur ein Wort in der Kette) = (26999/27000) ^ (n-1)

Es könnte allerdings mindestens ein Wort passen, das wäre dann das Gegenereignis (Gegenereignis und Ereignis haben zusammen immer die Wahrscheinlichkeit 1 bzw. 100%, sie decken gemeinsam alle Möglichkeiten ab)...

P(mindestens ein Wort passt als zweites) = 1 - P(nur ein Wort in der Kette)
= 1 - (26999/27000) ^ (n-1)

Die Wahrscheinlichkeit für das Gegenereignis ist allerdings verdammt nah an 0, also extrem unwahrscheinlich, solange n nicht einigermassen gross ist.

Nehmen wir mal an, der zweite Fall ist eingetreten, wir haben also ein passendes zweites Wort für die Kette gefunden.

3. Wort

Die Kandidatenschar ist schon leicht geschrumpft, es sind nur noch n-2. Interessant ist jetzt erstmal wieder, wie wahrscheinlich es ist, dass keins passt.

P(nur zwei Wörter in der Kette) = (26999/27000) ^ (n-2)

Wie eben können wir davon das Gegenereignis bilden.

P(mindestens ein Wort passt als drittes) = 1 - (26999/2700) ^ (n-2)

Dabei haben wir allerdings unterschlagen, dass überhaupt erstmal ein zweites Wort her muss, was ja garnicht sicher ist. Die Wahrscheinlichkeit von P(mindestens ein Wort passt als zweites) muss jeweils an P(nur zwei...) und an P(...als drittes) multipliziert werden, als Vorbedingung.

P(nur zwei...) = ( 1 - (26999/27000) ^ (n-1) ) * ( (26999/27000) ^ (n-2) )

P(... als drittes) = ( 1 - (26999/27000) ^ (n-1) ) * ( 1 - (26999/2700) ^ (n-2) )

Ich wechsle gleich zu zwei Beispielen, wird langsam unübersichtlich. Vorher noch schnell das...

4. Wort

P(nur drei...) = P(... als drittes) * (26999/27000) ^ (n-3)
P(...als viertes) = 1 - P(... als drittes) * (26999/27000) ^ (n-3)


Fortsetzung im nächsten Posting...

Wir haben nun für beliebige n die Wahrscheinlichkeiten, wie oft Wörterketten mit 1, 2, 3, ... Wörtern auftreten. Das ist nützlich, da wir so auch den Aufwand schätzen können.

Eine Wörterkette mit einem Wort brauchte nur Vergleiche mit n-1 Kandidaten für das zweite Wort (die alle negativ ausfielen). Eine Wörterkette mit zwei Wörtern musste das ebenfalls durchstehen, zusätzlich kam pro zweitem Wort nochmal n-2 Kandidaten für das dritte Wort in Frage. In Formeln gepackt...

Laufzeit(1-Wort-Kette) = (n-1) Vergleiche
Laufzeit(2-Wort-Kette) = (n-1) * (n-2) Vergleiche
Laufzeit(3-Wort-Kette) = (n-1) * (n-2) * (n-3) Vergleiche
...
Laufzeit(n-Wort-Kette) = (n-1) * (n-2) * ... * 1 Vergleiche

Da jedes der n Wörter als Startwort möglich ist, kommt nochmal ein Faktor *n dazu. Jedes zusätzliche Wort wird also mit einem hohen zusätzlichen Aufwand erkauft. Kommen wir zu den Beispielen...


n = 1025

Die Chance für eine 1-Wort-Kette war....

P(nur ein Wort in der Kette) = (26999/27000) ^ (n-1)

Das wäre in dem Fall (26999/27000) ^ 1024, rund 0.9628. Es ist also nicht sehr wahrscheinlich, dass man sich mit langen Ketten und schlechten Laufzeiten herumärgern muss. Falls das passiert, kann die Laufzeit aber schnell bösartig werden. n * (n-1) * (n-2) * (n-3) * (n-4) * (n-5) bei einer 5-Wort-Kette wären schon rund eine Trillion Operationen. Selbst wenn man für jeden Vergleich nur einen einzigen CPU-Takt bräuchte, müsste ein Rechner mit 1 GHz etwa eine Milliarde Sekunden, knapp 32 Jahre. Ohne Stromausfall, Blitzeinschläge oder Verschleiss.


n = 32769

P(nur ein Wort in der Kette) = (26999/27000) ^ (n-1)

Das wäre hier 0.2971. Mit mehr als 70%iger Wahrscheinlichkeit würde man also bei sovielen Wörtern Ketten mit mehr als einem Wort finden und entsprechend viel Aufwand haben. Rechenzeit einer 1 GHz CPU...

2-Wort-Kette: rund 35000 Sekunden (knapp 10 Stunden)
3-Wort-Kette: rund 1.15 Milliarden Sekunden (knapp 36.5 Jahre)
4-Wort-Kette: rund 37.8 Billionen Sekunden (knapp 1.2 Millionen Jahre)
5-Wort-Kette: da existiert das Universum nicht mehr


Je höher die n werden, desto höher wird der Aufwand für längere Ketten - und gleichzeitig treten sie öfter auf. Ich musste für meine Beispiele recht grosse Zahlen auspacken, in der Realität dürfte aber 1/27000 durch einen viel grösseren Wert ersetzt werden, da in keiner Sprache die Buchstaben gleichmässig verteilt sind. Damit müssten die Probleme schon deutlich früher auftreten.

Gute Nacht.

LOL? Laufzeitverhalten bei so nem Poplprogramm? haste nen 486er?

lol, von dem Thread wird man ja fast krank im kopf!
Naja, Leute, ihr habts schon drauf...
Wenn ich mal ne Visual Basic Frage habe(ham wir grad in der schule) komm ich zu euch^^
MfG

@Sheep
dein Laufzeitverhalten is zu hoch angesetzt, wenn mans richtig programmiert:

Wenn du die Wörter nach Anfangsbuchstaben unterteilst (Hashtable!, oder auch nen Suchbaum - is aber net so gut), brauchst jede Runde nur k Möglichkeiten Checken. Wobei k hier die durchschnittliche Anzahl der Wörter mit gleichem Anfang ist. Alle andren Möglichkeiten brauchst net checken, da die sicher keine gültige Lösung ergeben.

Für k = Länge der Längsten Kette ergibt sich ein Laufzeitverhalten von O(n*v^k). Das n steht da, weil man offensichtlich mit n-Verschiedenen Startwörtern anfangen kann.

Wenn man es gaaaanz genau nimmt hast du für extrem grosse n allerdings recht (da dort k~n, gibt ja "nur" 26^3 verschiedene Anfangskombos), aber für "kleinere" n is es zu pessimistisch, wobei es hier um "große" n ab ~10^10 Wörtern geht, wobei ich sagen würde das realistische Maximum an verschiedenen Wörtern liegt <1.000.000, jedenfalls aber deutlich unter 10^10


@MaxPower:

Quoted

ansonsten würden die schachcomputer auch nicht weltermeister besiegen Augenzwinkern

Wenn Schachcomputer ohne Heuristiken arbeiten würden, würden sie auch nie auf diese Leitung kommen Schachkomputer setzen extrem auf Heuristiken, um zu entscheiden bei welchen Zügen es sich lohnt sie weiter zu untersuchen. zB. die Bewertung von Stellung die Schachcomputer von sich geben sollte ja jeder der Schach spielt kennen - genau sowas läuft unter dem Titel Heuristik

@Asmo:

Quoted

LOL? Laufzeitverhalten bei so nem Poplprogramm? haste nen 486er? Augenzwinkern

Wenn du versuchen würdest mit allen PCs der Welt für die 300.000-Wörter Liste oben, die optimale Wortkette zu finden, würd die Lösung net vor Ende des Universums ausgespuckt werden

Wie komm ich drauf?

Meine Wortketten werden da so um 8800 Wörter lang. Wenn man davon ausgeht das die beste wahrscheinlich jenseits der 10.000 lang is, und man zumindest 2 (arge Untertreibung btw!) Entscheidungen pro Wört machen muss, kommt man auf 2^10.000 = 2x10^3000. Das würd dem Brute-Forcen eines 10.000 Bit Keys gleichkommen.

(Zur info: 128 Bit werden für die nächsten 10 Jahre als völlig unknackbar angesehn, und ein 10.000Bit key is ca 10^2970 mal schwerer )

ie, völlig egal ob mit nem 486'er oder nem Top-PC, oder allen Top-PCs der Welt: Für mehr als ein paar Wörter kannste für das Problem keine optimale Lösung finden.

@Ramses: In Prolog is es zwar leichter zu Proggen, die Laufzeit bleibt aber die selbe,...

Btw, meine Greedy-Search Lösung von oben sollte Laufzeit von ca O(n+v*k) haben - sollte also auch für grosse Ketten ne brauchbare Laufzeit haben:

Quoted

Matching Characters: 3
Minimum Word Length: 3
Reading mbsingle.txt.........
Splitting,...
Eliminating duplicates & short words,...
Wordlist has 350684 Words.
Reading File & creating Hashtable took us 4563ms

Using Greedy-Search we found a Chain with 8844 Words.
Search took us 1906ms.

Wrote Chain to mout.txt.

Ich würd diese oder ne ähnliche Lösung abgeben, denn ne vollständige Suche is sicherlich net machbar

Code: wordlist.java

Zip mit den andren Files & fertigem Jar is oben gelinkt...

Wenn sich jemand an nem bessren Suchalgorithmus probiern will, kann er gerne den Code als Basis nehmen.